12322 - Handgun Shooting Sport/ana.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 bool shot [1000];
  28 vector < pair <long double, long double> > angles;
  29
  30 void shoot(const long double &begin, const long double &end, const int &index){
  31         shot[index] = true;
  32         if (index < angles.size() - 1){
  33                 long double begin_next = angles[index + 1].first;
  34                 if (begin_next >= begin and begin_next <= end)
  35                                 shoot(begin_next, min(end, angles[index + 1].second) , index + 1);
  36         }
  37
  38 }
  39
  40 int main(){
  41         int B;
  42         while(cin >> B){
  43                 if (B == 0) break;
  44                 // Read billboards
  45                 angles.clear();
  46                 for (int i = 0; i < B; i++){
  47                         int x1, x2, y1, y2;
  48                         cin >> x1 >> y1 >> x2 >> y2;
  49                         //Convert to polar coordinates
  50                         long double angle1 = atan2((long double) y1, (long double) x1);
  51                         long double angle2 = atan2((long double) y2, (long double) x2);
  52                         angles.push_back(make_pair(min(angle1, angle2), max(angle1,angle2) ));
  53                 }
  54                 sort(angles.begin(), angles.end());
  55
  56                 /*for (int i = 0; i < B; i++){
  57                         cout << angles[i].first << "  " << angles[i].second << endl;
  58                 }*/
  59
  60                 for (int i = 0; i < B; i++) shot[i] = false;
  61                 int shots = 0;
  62                 for (int i = 0; i < B; i++){
  63                         if (!shot[i]){
  64                                 //printf("Shot billboard number %d\n", i);
  65                                 shots++;
  66                                 shoot(angles[i].first, angles[i].second, i);
  67                         }
  68                 }
  69                 cout << shots << endl;
  70         }
  71     return 0;
  72 }